package sorting;

import java.util.Comparator;
import java.util.Random;

/**
 * Created by Tzachi on 17/10/2014.
 *
 * Time complexity: O(n*logn)
 * Space complexity: O(n)
 */
public class QuickSort {
    public static final Random RND = new Random();
    private static void swap(Object[] array, int i, int j) {
        Object tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    private static <E> int partition(E[] array, int begin, int end, Comparator<? super E>  cmp) {
        int swapIndex = begin + RND.nextInt(end - begin + 1);
        E pivotValue = array[swapIndex];
        swap(array, swapIndex, end);
        for (int i = swapIndex = begin; i < end; ++ i) {
            if (cmp.compare(array[i], pivotValue) <= 0) {
                swap(array, swapIndex, i);
                swapIndex++;
            }
        }
        swap(array, swapIndex, end);
        return swapIndex;
    }
    private static <E> void quicksort(E[] array, int begin, int end, Comparator<? super E> cmp) {
        if (end > begin) {
            int index = partition(array, begin, end, cmp);
            quicksort(array, begin, index - 1, cmp);
            quicksort(array, index + 1, end, cmp);
        }
    }
    public static <E> void sort(E[] array, Comparator<? super E> cmp) {
        quicksort(array, 0, array.length - 1, cmp);
    }
}
